Раскраска двудольного графа в два цвета
Правильная вершинная рёберная раскраска — это раскраска вершин рёбер графа, при которой любые смежные вершины рёбра окрашены в разные цвета. Правильную вершинную раскраску часто называют просто раскраской графа. Граф называется k k k -раскрашиваемым, если существует правильная вершинная раскраска графа k k k цветами. Граф является 2 2 2 -хроматическим тогда и только тогда, когда он не содержит простых циклов нечётной длины.
Корректной раскраской графа в два цвета называется такая раскраска, что никакое ребро не соединяет две вершины одного цвета. Графы, которые можно так раскрасить, называют двудольными. Заметим, что если такая раскраска существует, и если зафиксировать цвет одной вершины, то все цвета всех достижимых из неё вершин определяются однозначно: пусть цвет этой вершины белый, тогда все её соседи будут иметь черный цвет, все вершины на расстоянии 2 будут иметь снова белый цвет, все вершины на расстоянии 3 снова черный, и так далее. Проверять граф на двудольность и выводить раскраску можно обходом в глубину. На этот раз наш dfs будет принимать параметром цвет, в который нужно покрасить вершину, и он будет рекурсивно запускаться от всех соседей, крася их в противоположный цвет. По окончании работы алгоритма мы либо обнаружим, что граф не двудолен мы когда-то посмотрели на две соседние вершины, которым нужно присвоить один и тот же цвет , либо найдём разбиение вершин графа на две доли.
Раскраска графа это такая разметка графа, при которой любым двум смежным вершинам соответствуют разные цвета. Так как раскрасок графа может быть множество, то чаще всего интересует раскраска графа минимальным количеством цветов. Для раскраски графов сервис использует Жадный алгоритм. По этой причине для некоторых случаев алгоритм может находить близкое к минимального количеству цветов, но не самое минимальное.
